/* 710. 黑名单中的随机数 */
/**
 * @param {number} n
 * @param {number[]} blacklist
 */
/* 黑名单映射 */
var Solution = function (n, blacklist) {
	this.b2w = new Map()
	const m = blacklist.length

	/* 
        对于[0,n-m)范围内的黑名单可以映射到
        [n-m,n)范围的白名单
    */
	this.bound = n - m
	const black = new Set()
	for (const b of blacklist) {
		if (b >= this.bound) {
			/* [n-m,n)范围内的黑名单 */
			black.add(b)
		}
	}
	let w = this.bound
	for (const b of blacklist) {
		/* 
            [0,n-m) 不断增加w 直至其不在黑名单中
        */
		if (b < this.bound) {
			while (black.has(w)) {
				++w
			}
			this.b2w.set(b, w)
			++w
		}
	}
}

/**
 * @return {number}
 */
Solution.prototype.pick = function () {
	const x = Math.floor(Math.random() * this.bound)
	return this.b2w.get(x) || x
}
var solution = new Solution(7, [2, 3, 5])

const res = solution.pick()
console.log('solution <<', res)
